//题目:
// 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
// 说明：每次只能向下或者向右移动一步。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m=grid.size(),n=grid[0].size();
        //1.创建dp表————dp[i][j]表示：从初始位置到(i,j)位置的最小路径和
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //2.初始化
        for(int i=2;i<=m;i++) dp[i][0]=0xffffff;
        for(int j=2;j<=n;j++) dp[0][j]=0xffffff;
        //3.填表————动态转移方程：dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=grid[i-1][j-1]+min(dp[i-1][j],dp[i][j-1]);
            }
        }
        //4.确定返回值
        return dp[m][n];
    }
};